<!DOCTYPE html>
<html lang=zh>
<head>
  <meta charset="utf-8">
  
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, minimum-scale=1, user-scalable=no, minimal-ui">
  <meta name="renderer" content="webkit">
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black">
  <meta name="format-detection" content="telephone=no,email=no,adress=no">
  <!-- Color theme for statusbar -->
  <meta name="theme-color" content="#000000" />
  <!-- 强制页面在当前窗口以独立页面显示,防止别人在框架里调用页面 -->
  <meta http-equiv="window-target" content="_top" />
  
  
  <title>redis底层数据结构 | 逸辰</title>
  <meta name="description" content="redis底层数据结构动态字符串（SDS）字符串是redis中最常用的一种数据结构，不过Redis没有直接使用C语言中的字符串，因为C语言字符存在很多问题，比如：  获取字符串长度需要运算 非二进制安全（以”\0”作为结束标识） 不可修改  Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。 Redis是C语言实现的，其中SDS是一个">
<meta property="og:type" content="article">
<meta property="og:title" content="redis底层数据结构">
<meta property="og:url" content="https://yichenfirst.github.io/2023/03/20/redis/redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="逸辰">
<meta property="og:description" content="redis底层数据结构动态字符串（SDS）字符串是redis中最常用的一种数据结构，不过Redis没有直接使用C语言中的字符串，因为C语言字符存在很多问题，比如：  获取字符串长度需要运算 非二进制安全（以”\0”作为结束标识） 不可修改  Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。 Redis是C语言实现的，其中SDS是一个">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190651.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190654.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190658.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190701.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190705.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190708.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190712.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190719.gif">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190724.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190729.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190733.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190737.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190740.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190743.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190747.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190751.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190755.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190759.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190804.gif">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190811.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190816.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190821.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190827.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190832.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190835.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190840.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190844.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190848.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190851.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190855.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190859.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190903.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190906.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190911.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190918.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190921.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190923.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190926.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190928.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190931.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190933.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190936.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190938.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190940.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190944.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190949.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190952.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190954.png">
<meta property="og:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190958.png">
<meta property="article:published_time" content="2023-03-19T16:00:00.000Z">
<meta property="article:modified_time" content="2023-07-17T13:41:27.774Z">
<meta property="article:author" content="逸辰">
<meta property="article:tag" content="redis">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190651.png">
  <!-- Canonical links -->
  <link rel="canonical" href="https://yichenfirst.github.io/2023/03/20/redis/redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
  
    <link rel="alternate" href="/atom.xml" title="逸辰" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png" type="image/x-icon">
  
  
<link rel="stylesheet" href="/css/style.css">

  
  
  
  
<meta name="generator" content="Hexo 6.3.0">
<style>.github-emoji { position: relative; display: inline-block; width: 1.2em; min-height: 1.2em; overflow: hidden; vertical-align: top; color: transparent; }  .github-emoji > span { position: relative; z-index: 10; }  .github-emoji img, .github-emoji .fancybox { margin: 0 !important; padding: 0 !important; border: none !important; outline: none !important; text-decoration: none !important; user-select: none !important; cursor: auto !important; }  .github-emoji img { height: 1.2em !important; width: 1.2em !important; position: absolute !important; left: 50% !important; top: 50% !important; transform: translate(-50%, -50%) !important; user-select: none !important; cursor: auto !important; } .github-emoji-fallback { color: inherit; } .github-emoji-fallback img { opacity: 0 !important; }</style>
</head>


<body class="main-center" itemscope itemtype="http://schema.org/WebPage">
  <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  <div class="slimContent">
    <div class="navbar-header">
      
      
      <div class="profile-block text-center">
        <a id="avatar" href="" target="_blank">
          <img class="img-circle img-rotate" src="/images/avatar.jpg" width="200" height="200">
        </a>
        <h2 id="name" class="hidden-xs hidden-sm">逸辰</h2>
        <h3 id="title" class="hidden-xs hidden-sm hidden-md">后端开发</h3>
        <small id="location" class="text-muted hidden-xs hidden-sm"><i class="icon icon-map-marker"></i> 长春，中国</small>
      </div>
      
      <div class="search" id="search-form-wrap">

    <form class="search-form sidebar-form">
        <div class="input-group">
            <input type="text" class="search-form-input form-control" placeholder="搜索" />
            <span class="input-group-btn">
                <button type="submit" class="search-form-submit btn btn-flat" onclick="return false;"><i class="icon icon-search"></i></button>
            </span>
        </div>
    </form>
    <div class="ins-search">
  <div class="ins-search-mask"></div>
  <div class="ins-search-container">
    <div class="ins-input-wrapper">
      <input type="text" class="ins-search-input" placeholder="想要查找什么..." x-webkit-speech />
      <button type="button" class="close ins-close ins-selectable" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
    </div>
    <div class="ins-section-wrapper">
      <div class="ins-section-container"></div>
    </div>
  </div>
</div>


</div>
      <button class="navbar-toggle collapsed" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
      </button>
    </div>
    <nav id="main-navbar" class="collapse navbar-collapse" itemscope itemtype="http://schema.org/SiteNavigationElement" role="navigation">
      <ul class="nav navbar-nav main-nav ">
        
        
        <li class="menu-item menu-item-home">
          <a href="/.">
            
            <i class="icon icon-home-fill"></i>
            
            <span class="menu-title">首页</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-archives">
          <a href="/archives">
            
            <i class="icon icon-archives-fill"></i>
            
            <span class="menu-title">归档</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-categories">
          <a href="/categories">
            
            <i class="icon icon-folder"></i>
            
            <span class="menu-title">分类</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-tags">
          <a href="/tags">
            
            <i class="icon icon-tags"></i>
            
            <span class="menu-title">标签</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-about">
          <a href="/about">
            
            <i class="icon icon-cup-fill"></i>
            
            <span class="menu-title">关于</span>
          </a>
        </li>
        
      </ul>
      
    </nav>
  </div>
</header>

  
    <aside class="sidebar" itemscope itemtype="http://schema.org/WPSideBar">
  <div class="slimContent">
    
      <div class="widget">
    <h3 class="widget-title">公告</h3>
    <div class="widget-body">
        <div id="board">
            <div class="content">
                <p>欢迎交流与分享经验!</p>
            </div>
        </div>
    </div>
</div>

    
      
  <div class="widget">
    <h3 class="widget-title">分类</h3>
    <div class="widget-body">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/ElasticSearch/">ElasticSearch</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/docker/">docker</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/go/">go</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/java/">java</a><span class="category-list-count">6</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/mybatis/">mybatis</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/mysql/">mysql</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/redis/">redis</a><span class="category-list-count">6</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/spring/">spring</a><span class="category-list-count">9</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/vue/">vue</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F/">分布式</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">操作系统</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C/">计算机网络</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E9%9D%A2%E8%AF%95/">面试</a><span class="category-list-count">3</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">标签</h3>
    <div class="widget-body">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/ElasticSearch/" rel="tag">ElasticSearch</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/aop/" rel="tag">aop</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/docker/" rel="tag">docker</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/go/" rel="tag">go</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/java/" rel="tag">java</a><span class="tag-list-count">7</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/javascript/" rel="tag">javascript</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/mybatis/" rel="tag">mybatis</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/mysql/" rel="tag">mysql</a><span class="tag-list-count">5</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/redis/" rel="tag">redis</a><span class="tag-list-count">6</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/spring/" rel="tag">spring</a><span class="tag-list-count">9</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/springcloud/" rel="tag">springcloud</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/springsecurity/" rel="tag">springsecurity</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tcp/" rel="tag">tcp</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/token/" rel="tag">token</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/vue/" rel="tag">vue</a><span class="tag-list-count">4</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E6%80%BB%E7%BB%93/" rel="tag">总结</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" rel="tag">操作系统</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E9%9D%A2%E8%AF%95/" rel="tag">面试</a><span class="tag-list-count">1</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">标签云</h3>
    <div class="widget-body tagcloud">
      <a href="/tags/ElasticSearch/" style="font-size: 13px;">ElasticSearch</a> <a href="/tags/aop/" style="font-size: 13px;">aop</a> <a href="/tags/docker/" style="font-size: 13px;">docker</a> <a href="/tags/go/" style="font-size: 13px;">go</a> <a href="/tags/java/" style="font-size: 13.86px;">java</a> <a href="/tags/javascript/" style="font-size: 13px;">javascript</a> <a href="/tags/mybatis/" style="font-size: 13px;">mybatis</a> <a href="/tags/mysql/" style="font-size: 13.57px;">mysql</a> <a href="/tags/redis/" style="font-size: 13.71px;">redis</a> <a href="/tags/spring/" style="font-size: 14px;">spring</a> <a href="/tags/springcloud/" style="font-size: 13px;">springcloud</a> <a href="/tags/springsecurity/" style="font-size: 13px;">springsecurity</a> <a href="/tags/tcp/" style="font-size: 13px;">tcp</a> <a href="/tags/token/" style="font-size: 13px;">token</a> <a href="/tags/vue/" style="font-size: 13.43px;">vue</a> <a href="/tags/%E6%80%BB%E7%BB%93/" style="font-size: 13.14px;">总结</a> <a href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" style="font-size: 13.29px;">操作系统</a> <a href="/tags/%E9%9D%A2%E8%AF%95/" style="font-size: 13px;">面试</a>
    </div>
  </div>

    
      
  <div class="widget">
    <h3 class="widget-title">归档</h3>
    <div class="widget-body">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/09/">九月 2023</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/07/">七月 2023</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/05/">五月 2023</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/04/">四月 2023</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/03/">三月 2023</a><span class="archive-list-count">5</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/02/">二月 2023</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/01/">一月 2023</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/12/">十二月 2022</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/11/">十一月 2022</a><span class="archive-list-count">4</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/10/">十月 2022</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/09/">九月 2022</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/08/">八月 2022</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/06/">六月 2022</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/04/">四月 2022</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/02/">二月 2022</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/01/">一月 2022</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/10/">十月 2021</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/09/">九月 2021</a><span class="archive-list-count">3</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/08/">八月 2021</a><span class="archive-list-count">3</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/07/">七月 2021</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/06/">六月 2021</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/03/">三月 2021</a><span class="archive-list-count">2</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget-body">
      <ul class="recent-post-list list-unstyled no-thumbnail">
        
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F/">分布式</a>
              </p>
              <p class="item-title">
                <a href="/2023/09/01/%E5%88%86%E5%B8%83%E5%BC%8F/%E5%88%86%E5%B8%83%E5%BC%8F%E4%BA%8B%E5%8A%A1/" class="title">分布式事务</a>
              </p>
              <p class="item-date">
                <time datetime="2023-09-01T08:53:49.259Z" itemprop="datePublished">2023-09-01</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/categories/java/">java</a>
              </p>
              <p class="item-title">
                <a href="/2023/07/28/java/Java%E7%BA%BF%E7%A8%8B%E6%A8%A1%E5%9E%8B/" class="title">Java线程模型</a>
              </p>
              <p class="item-date">
                <time datetime="2023-07-28T13:59:18.661Z" itemprop="datePublished">2023-07-28</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/categories/java/">java</a>
              </p>
              <p class="item-title">
                <a href="/2023/05/19/java/AQS/" class="title">AQS详解</a>
              </p>
              <p class="item-date">
                <time datetime="2023-05-18T16:00:00.000Z" itemprop="datePublished">2023-05-19</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/categories/go/">go</a>
              </p>
              <p class="item-title">
                <a href="/2023/05/03/go/new%E4%B8%8Emake%E5%85%B3%E9%94%AE%E5%AD%97%E7%9A%84%E5%8C%BA%E5%88%AB/" class="title">new与make关键字的区别</a>
              </p>
              <p class="item-date">
                <time datetime="2023-05-02T16:00:00.000Z" itemprop="datePublished">2023-05-03</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/categories/java/">java</a>
              </p>
              <p class="item-title">
                <a href="/2023/04/15/java/CAS/" class="title">CAS</a>
              </p>
              <p class="item-date">
                <time datetime="2023-04-14T16:00:00.000Z" itemprop="datePublished">2023-04-15</time>
              </p>
            </div>
          </li>
          
      </ul>
    </div>
  </div>
  

    
  </div>
</aside>

  
  
<main class="main" role="main">
  <div class="content">
  <article id="post-redis/redis底层数据结构" class="article article-type-post" itemscope itemtype="http://schema.org/BlogPosting">
    
    <div class="article-header">
      
        
  
    <h1 class="article-title" itemprop="name">
      redis底层数据结构
    </h1>
  

      
      <div class="article-meta">
        <span class="article-date">
    <i class="icon icon-calendar-check"></i>
	<a href="/2023/03/20/redis/redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" class="article-date">
	  <time datetime="2023-03-19T16:00:00.000Z" itemprop="datePublished">2023-03-20</time>
	</a>
</span>
        
  <span class="article-category">
    <i class="icon icon-folder"></i>
    <a class="article-category-link" href="/categories/redis/">redis</a>
  </span>

        
  <span class="article-tag">
    <i class="icon icon-tags"></i>
	<a class="article-tag-link-link" href="/tags/redis/" rel="tag">redis</a>
  </span>


        
	<span class="article-read hidden-xs">
	    <i class="icon icon-eye-fill" aria-hidden="true"></i>
	    <span id="busuanzi_container_page_pv">
			<span id="busuanzi_value_page_pv">0</span>
		</span>
	</span>


        <span class="post-comment"><i class="icon icon-comment"></i> <a href="/2023/03/20/redis/redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/#comments" class="article-comment-link">评论</a></span>
        
	
		<span class="post-wordcount hidden-xs" itemprop="wordCount">字数统计: 5.2k(字)</span>
	
	
		<span class="post-readcount hidden-xs" itemprop="timeRequired">阅读时长: 19(分)</span>
	

      </div>
    </div>
    <div class="article-entry marked-body" itemprop="articleBody">
      
        <h2 id="redis底层数据结构"><a href="#redis底层数据结构" class="headerlink" title="redis底层数据结构"></a>redis底层数据结构</h2><h3 id="动态字符串（SDS）"><a href="#动态字符串（SDS）" class="headerlink" title="动态字符串（SDS）"></a>动态字符串（SDS）</h3><p>字符串是redis中最常用的一种数据结构，不过Redis没有直接使用C语言中的字符串，因为C语言字符存在很多问题，比如：</p>
<ul>
<li>获取字符串长度需要运算</li>
<li>非二进制安全（以”\0”作为结束标识）</li>
<li>不可修改</li>
</ul>
<p>Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。</p>
<p>Redis是C语言实现的，其中SDS是一个结构体，源码如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190651.png" alt="image-20230705145038398"></p>
<p>例如，一个包含字符串”name”的sds结构如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190654.png" alt="image-20230705145430491"></p>
<p>sds之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为”hi”的sds：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190658.png" alt="image-20230705145627005"></p>
<p>假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：</p>
<p>如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；</p>
<p>如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190701.png" alt="image-20230705150401932"></p>
<p>sds优点：</p>
<ul>
<li>获取字符串长度的时间复杂度为O(1)</li>
<li>支持动态扩容</li>
<li>减少内存分配次数</li>
</ul>
<h3 id="IntSet"><a href="#IntSet" class="headerlink" title="IntSet"></a>IntSet</h3><p>IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。</p>
<p>结构如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190705.png" alt="image-20230705151114910"></p>
<p>其中的encoding包含三种模式，表示存储的整数大小不同：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190708.png" alt="image-20230705151135552"></p>
<p>为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190712.png" alt="image-20230705151654522"></p>
<p>现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：</p>
<ul>
<li><p>encoding：4字节</p>
</li>
<li><p>length：4字节</p>
</li>
<li><p>contents：2字节 * 3  = 6字节</p>
</li>
</ul>
<p>现在，假设有一个intset，元素为{5,10，20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190719.gif" alt="tutieshi_640x65_15s"></p>
<p>我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动<strong>升级</strong>编码方式到合适的大小。</p>
<p>以当前案例来说流程如下：</p>
<p>①升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组</p>
<p>②倒序依次将数组中的元素拷贝到扩容后的正确位置</p>
<p>③将待添加的元素放入数组末尾</p>
<p>④最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190724.png" alt="image-20230705153041938"></p>
<p><strong>总结：</strong></p>
<p>IntSet可以看做是特殊的整数数据，具备一下特点：</p>
<ul>
<li>Redis会确保IntSet中的元素唯一、有序</li>
<li>具备类型升级，可以节省内存空间</li>
<li>底层采用二分查找方式来查询</li>
</ul>
<h3 id="Dict"><a href="#Dict" class="headerlink" title="Dict"></a>Dict</h3><p>我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。</p>
<p>Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190729.png" alt="image-20230705154452696"></p>
<p>当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h &amp; sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1，假设k1的哈希值h =1，则1&amp;3 =1，因此k1=v1要存储到数组角标1位置。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190733.png" alt="image-20230705155434157"></p>
<p>现在有一个键值对k2=v2经过hash运算后，也要存到数据下标为1的位置，此时就发生了冲突，如下图，使用头插法。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190737.png" alt="image-20230705155634102"></p>
<p>上面介绍了Dict的哈希表（DictHashTable）和哈希节点（DictEntry），剩下的字典（Dict）结构如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190740.png" alt="image-20230705160153526"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190743.png" alt="image-20230705160353027"></p>
<blockquote>
<p>Dict的扩容</p>
</blockquote>
<p>Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。</p>
<p>Dict在每次新增键值对时都会检查<strong>负载因子</strong>（LoadFactor = used/size） ，满足以下两种情况时会触发<strong>哈希表扩容</strong>：</p>
<ul>
<li><p>哈希表的 LoadFactor &gt;= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；</p>
</li>
<li><p>哈希表的 LoadFactor &gt; 5 ；</p>
</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190747.png" alt="image-20230705161337183"></p>
<blockquote>
<p>Dict的收缩</p>
</blockquote>
<p>Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor &lt; 0.1 时，会做哈希表收缩：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190751.png" alt="image-20230705161930438"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190755.png" alt="image-20230705161950225"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190759.png" alt="image-20230705162004337"></p>
<blockquote>
<p>Dict的rehash</p>
</blockquote>
<p>不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为<strong>rehash</strong>。过程是这样的：</p>
<p>①计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：</p>
<ul>
<li><p>如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n</p>
</li>
<li><p>如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）</p>
</li>
</ul>
<p>②按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]</p>
<p>③设置dict.rehashidx = 0，标示开始rehash</p>
<p>④将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]</p>
<p>⑤将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190804.gif" alt="tutieshi_640x344_28s"></p>
<blockquote>
<p>Dict的渐进式rehash</p>
</blockquote>
<p>Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为<strong>渐进式rehash</strong>。流程如下：</p>
<p>①计算新hash表的size，值取决于当前要做的是扩容还是收缩：</p>
<ul>
<li><p>如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的$2^n$</p>
</li>
<li><p>如果是收缩，则新size为第一个大于等于dict.ht[0].used的$2^n $（不得小于4）</p>
</li>
</ul>
<p>②按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]</p>
<p>③设置dict.rehashidx = 0，标示开始rehash</p>
<p>④<strong>每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]</strong></p>
<p>⑤将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存</p>
<p>⑥<strong>将rehashidx赋值为-1，代表rehash结束</strong></p>
<p>⑦<strong>在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空</strong></p>
<p><strong>总结：</strong></p>
<p>Dict的结构：</p>
<ul>
<li><p>类似java的HashTable，底层是数组加链表来解决哈希冲突</p>
</li>
<li><p>Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash</p>
</li>
</ul>
<p>Dict的伸缩：</p>
<ul>
<li><p>当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容</p>
</li>
<li><p>当LoadFactor小于0.1时，Dict收缩</p>
</li>
<li><p>扩容大小为第一个大于等于used + 1的$2^n$</p>
</li>
<li><p>收缩大小为第一个大于等于used 的$2^n$</p>
</li>
<li><p>Dict采用渐进式rehash，每次访问Dict时执行一次rehash</p>
</li>
<li><p>rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表</p>
</li>
</ul>
<h3 id="ZipList"><a href="#ZipList" class="headerlink" title="ZipList"></a>ZipList</h3><p> <strong>ZipList</strong> 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190811.png" alt="1653985987327"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190816.png" alt="1653986020491"></p>
<table>
<thead>
<tr>
<th><strong>属性</strong></th>
<th><strong>类型</strong></th>
<th><strong>长度</strong></th>
<th><strong>用途</strong></th>
</tr>
</thead>
<tbody><tr>
<td>zlbytes</td>
<td>uint32_t</td>
<td>4 字节</td>
<td>记录整个压缩列表占用的内存字节数</td>
</tr>
<tr>
<td>zltail</td>
<td>uint32_t</td>
<td>4 字节</td>
<td>记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。</td>
</tr>
<tr>
<td>zllen</td>
<td>uint16_t</td>
<td>2 字节</td>
<td>记录了压缩列表包含的节点数量。 最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。</td>
</tr>
<tr>
<td>entry</td>
<td>列表节点</td>
<td>不定</td>
<td>压缩列表包含的各个节点，节点的长度由节点保存的内容决定。</td>
</tr>
<tr>
<td>zlend</td>
<td>uint8_t</td>
<td>1 字节</td>
<td>特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。</td>
</tr>
</tbody></table>
<blockquote>
<p>ZipListEntry</p>
</blockquote>
<p>ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190821.png" alt="1653986055253"></p>
<ul>
<li><p>previous_entry_length：前一节点的长度，占1个或5个字节。</p>
<ul>
<li>如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值</li>
<li>如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据</li>
</ul>
</li>
<li><p>encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节</p>
</li>
<li><p>contents：负责保存节点的数据，可以是字符串或整数</p>
</li>
</ul>
<p>ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412</p>
<blockquote>
<p>Encoding编码</p>
</blockquote>
<p>ZipListEntry中的encoding编码分为字符串和整数两种：<br>字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串</p>
<table>
<thead>
<tr>
<th><strong>编码</strong></th>
<th><strong>编码长度</strong></th>
<th><strong>字符串大小</strong></th>
</tr>
</thead>
<tbody><tr>
<td>|00pppppp|</td>
<td>1 bytes</td>
<td>&lt;= 63 bytes</td>
</tr>
<tr>
<td>|01pppppp|qqqqqqqq|</td>
<td>2 bytes</td>
<td>&lt;= 16383 bytes</td>
</tr>
<tr>
<td>|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|</td>
<td>5 bytes</td>
<td>&lt;= 4294967295 bytes</td>
</tr>
</tbody></table>
<p>例如，我们要保存字符串：“ab”和 “bc”</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190827.png" alt="1653986132019"></p>
<p> ZipListEntry中的encoding编码分为字符串和整数两种：</p>
<ul>
<li>整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节</li>
</ul>
<table>
<thead>
<tr>
<th><strong>编码</strong></th>
<th><strong>编码长度</strong></th>
<th><strong>整数类型</strong></th>
</tr>
</thead>
<tbody><tr>
<td>11000000</td>
<td>1</td>
<td>int16_t（2 bytes）</td>
</tr>
<tr>
<td>11010000</td>
<td>1</td>
<td>int32_t（4 bytes）</td>
</tr>
<tr>
<td>11100000</td>
<td>1</td>
<td>int64_t（8 bytes）</td>
</tr>
<tr>
<td>11110000</td>
<td>1</td>
<td>24位有符整数(3 bytes)</td>
</tr>
<tr>
<td>11111110</td>
<td>1</td>
<td>8位有符整数(1 bytes)</td>
</tr>
<tr>
<td>1111xxxx</td>
<td>1</td>
<td>直接在xxxx位置保存数值，范围从0001~1101，减1后结果为实际值</td>
</tr>
</tbody></table>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190832.png" alt="1653986172002"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190835.png" alt="1653986209718"></p>
<blockquote>
<p>ZipList的连锁更新问题</p>
</blockquote>
<p>ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：<br>如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值<br>如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据<br>现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190840.png" alt="1653986217182"></p>
<p>ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。</p>
<p><strong>ZipList特性：</strong></p>
<ul>
<li>压缩列表的可以看做一种连续内存空间的”双向链表”</li>
<li>列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低</li>
<li>如果列表数据过多，导致链表过长，可能影响查询性能</li>
<li>增或删较大数据时有可能发生连续更新问题</li>
</ul>
<h3 id="QuickList"><a href="#QuickList" class="headerlink" title="QuickList"></a>QuickList</h3><p>问题1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？</p>
<p>​	答：为了缓解这个问题，我们必须限制ZipList的长度和entry大小。</p>
<p>问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？</p>
<p>​	答：我们可以创建多个ZipList来分片存储数据。</p>
<p>问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？</p>
<p>​	答：Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190844.png" alt="1653986474927"></p>
<p>为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。<br>如果值为正，则代表ZipList的允许的entry个数的最大值<br>如果值为负，则代表ZipList的最大内存大小，分5种情况：</p>
<ul>
<li>-1：每个ZipList的内存占用不能超过4kb</li>
<li>-2：每个ZipList的内存占用不能超过8kb</li>
<li>-3：每个ZipList的内存占用不能超过16kb</li>
<li>-4：每个ZipList的内存占用不能超过32kb</li>
<li>-5：每个ZipList的内存占用不能超过64kb</li>
</ul>
<p>其默认值为 -2：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190848.png" alt="1653986642777"></p>
<p>以下是QuickList的和QuickListNode的结构源码：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190851.png" alt="1653986667228"></p>
<p>我们接下来用一段流程图来描述当前的这个结构</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190855.png" alt="1653986718554"></p>
<p>总结：</p>
<p>QuickList的特点：</p>
<ul>
<li>是一个节点为ZipList的双端链表</li>
<li>节点采用ZipList，解决了传统链表的内存占用问题</li>
<li>控制了ZipList大小，解决连续内存空间申请效率问题</li>
<li>中间节点可以压缩，进一步节省了内存</li>
</ul>
<h3 id="SkipList"><a href="#SkipList" class="headerlink" title="SkipList"></a>SkipList</h3><p>SkipList（跳表）首先是链表，但与传统链表相比有几点差异：<br>元素按照升序排列存储<br>节点可能包含多个指针，指针跨度不同。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190859.png" alt="1653986771309"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190903.png" alt="1653986813240"></p>
<p>SkipList（跳表）首先是链表，但与传统链表相比有几点差异：<br>元素按照升序排列存储<br>节点可能包含多个指针，指针跨度不同。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190906.png" alt="1653986877620"></p>
<p>小总结：</p>
<p>SkipList的特点：</p>
<ul>
<li>跳跃表是一个双向链表，每个节点都包含score和ele值</li>
<li>节点按照score值排序，score值一样则按照ele字典排序</li>
<li>每个节点都可以包含多层指针，层数是1到32之间的随机数</li>
<li>不同层指针到下一个节点的跨度不同，层级越高，跨度越大</li>
<li>增删改查效率与红黑树基本一致，实现却更简单</li>
</ul>
<h3 id="RedisObject"><a href="#RedisObject" class="headerlink" title="RedisObject"></a>RedisObject</h3><p>Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下：</p>
<p>1、什么是redisObject：<br>从Redis的使用者的角度来看，⼀个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从key space到object space的映射关系。这个映射关系的key是string类型，⽽value可以是多种数据类型，比如：<br>string, list, hash、set、sorted set等。我们可以看到，key的类型固定是string，而value可能的类型是多个。<br>⽽从Redis内部实现的⾓度来看，database内的这个映射关系是用⼀个dict来维护的。dict的key固定用⼀种数据结构来表达就够了，这就是动态字符串sds。而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是robj，全名是redisObject。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190911.png" alt="1653986956618"></p>
<p>Redis的编码方式</p>
<p>Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：</p>
<table>
<thead>
<tr>
<th><strong>编号</strong></th>
<th><strong>编码方式</strong></th>
<th><strong>说明</strong></th>
</tr>
</thead>
<tbody><tr>
<td>0</td>
<td>OBJ_ENCODING_RAW</td>
<td>raw编码动态字符串</td>
</tr>
<tr>
<td>1</td>
<td>OBJ_ENCODING_INT</td>
<td>long类型的整数的字符串</td>
</tr>
<tr>
<td>2</td>
<td>OBJ_ENCODING_HT</td>
<td>hash表（字典dict）</td>
</tr>
<tr>
<td>3</td>
<td>OBJ_ENCODING_ZIPMAP</td>
<td>已废弃</td>
</tr>
<tr>
<td>4</td>
<td>OBJ_ENCODING_LINKEDLIST</td>
<td>双端链表</td>
</tr>
<tr>
<td>5</td>
<td>OBJ_ENCODING_ZIPLIST</td>
<td>压缩列表</td>
</tr>
<tr>
<td>6</td>
<td>OBJ_ENCODING_INTSET</td>
<td>整数集合</td>
</tr>
<tr>
<td>7</td>
<td>OBJ_ENCODING_SKIPLIST</td>
<td>跳表</td>
</tr>
<tr>
<td>8</td>
<td>OBJ_ENCODING_EMBSTR</td>
<td>embstr的动态字符串</td>
</tr>
<tr>
<td>9</td>
<td>OBJ_ENCODING_QUICKLIST</td>
<td>快速列表</td>
</tr>
<tr>
<td>10</td>
<td>OBJ_ENCODING_STREAM</td>
<td>Stream流</td>
</tr>
</tbody></table>
<p>五种数据结构</p>
<p>Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：</p>
<table>
<thead>
<tr>
<th><strong>数据类型</strong></th>
<th><strong>编码方式</strong></th>
</tr>
</thead>
<tbody><tr>
<td>OBJ_STRING</td>
<td>int、embstr、raw</td>
</tr>
<tr>
<td>OBJ_LIST</td>
<td>LinkedList和ZipList(3.2以前)、QuickList（3.2以后）</td>
</tr>
<tr>
<td>OBJ_SET</td>
<td>intset、HT</td>
</tr>
<tr>
<td>OBJ_ZSET</td>
<td>ZipList、HT、SkipList</td>
</tr>
<tr>
<td>OBJ_HASH</td>
<td>ZipList、HT</td>
</tr>
</tbody></table>
<h2 id="Redis基础数据结构的实现"><a href="#Redis基础数据结构的实现" class="headerlink" title="Redis基础数据结构的实现"></a>Redis基础数据结构的实现</h2><h3 id="String"><a href="#String" class="headerlink" title="String"></a>String</h3><p>String是Redis中最常见的数据存储类型：</p>
<ul>
<li><p>其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。</p>
</li>
<li><p>如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。</p>
</li>
<li><p>如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。</p>
</li>
</ul>
<p>底层实现⽅式：动态字符串sds 或者 long<br>String的内部存储结构⼀般是sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个String类型的value的值是数字，那么Redis内部会把它转成long类型来存储，从⽽减少内存的使用。</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190918.png" alt="1653987103450"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190921.png" alt="image-20230707143910432"></p>
<h3 id="List"><a href="#List" class="headerlink" title="List"></a>List</h3><p>Redis的List类型可以从首、尾操作列表中的元素：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190923.png" alt="1653987240622"></p>
<ul>
<li>LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多</li>
<li>ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低</li>
<li>QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高</li>
</ul>
<p>Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：</p>
<p>在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。</p>
<p>在3.2版本之后，Redis统一采用QuickList来实现List：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190926.png" alt="1653987313461"></p>
<h3 id="Set"><a href="#Set" class="headerlink" title="Set"></a>Set</h3><p>Set是Redis中的单列集合，满足下列特点：</p>
<ul>
<li>不保证有序性</li>
<li>保证元素唯一</li>
<li>求交集、并集、差集</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190928.png" alt="1653987342550"></p>
<p>可以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？<br>HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）</p>
<p>Set是Redis中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。</p>
<ul>
<li>为了查询效率和唯一性，<strong>set采用HT编码（Dict</strong>）。Dict中的key用来存储元素，value统一为null。</li>
<li>当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，<strong>Set会采用IntSet编码</strong>，以节省内存</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190931.png" alt="1653987388177"></p>
<p>结构如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190933.png" alt="1653987454403"></p>
<h3 id="Zset"><a href="#Zset" class="headerlink" title="Zset"></a>Zset</h3><p>ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值：</p>
<ul>
<li>可以根据score值排序后</li>
<li>member必须唯一</li>
<li>可以根据member查询分数</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190936.png" alt="1653992091967"></p>
<p>因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？</p>
<ul>
<li>SkipList：可以排序，并且可以同时存储score和ele值（member）</li>
<li>HT（Dict）：可以键值存储，并且可以根据key找value</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190938.png" alt="1653992121692"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190940.png" alt="1653992172526"></p>
<p>当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此<strong>zset还会采用ZipList结构来节省内存</strong>，不过需要同时满足两个条件：</p>
<ul>
<li>元素数量小于zset_max_ziplist_entries，默认值128</li>
<li>每个元素都小于zset_max_ziplist_value字节，默认值64</li>
</ul>
<p>ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：</p>
<ul>
<li>ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后</li>
<li>score越小越接近队首，score越大越接近队尾，按照score值升序排列</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190944.png" alt="1653992238097"></p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190949.png" alt="1653992299740"></p>
<h3 id="Hash"><a href="#Hash" class="headerlink" title="Hash"></a>Hash</h3><p>Hash结构与Redis中的Zset非常类似：</p>
<ul>
<li>都是键值存储</li>
<li>都需求根据键获取值</li>
<li>键必须唯一</li>
</ul>
<p>区别如下：</p>
<ul>
<li>zset的键是member，值是score；hash的键和值都是任意值</li>
<li>zset要根据score排序；hash则无需排序</li>
</ul>
<p>（1）底层实现方式：<strong>压缩列表ziplist 或者 字典dict</strong><br>当Hash中数据项比较少的情况下，Hash底层才⽤压缩列表ziplist进⾏存储数据，随着数据的增加，底层的ziplist就可能会转成dict，具体配置如下：</p>
<ul>
<li>hash-max-ziplist-entries 512</li>
<li>hash-max-ziplist-value 64</li>
</ul>
<p>当满足上面两个条件其中之⼀的时候，Redis就使⽤dict字典来实现hash。<br>Redis的hash之所以这样设计，是因为当ziplist变得很⼤的时候，它有如下几个缺点：</p>
<ul>
<li>每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝，从而降低性能。</li>
<li>⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据。</li>
<li>当ziplist数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。</li>
</ul>
<p>总之，ziplist本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存realloc，可能导致内存拷贝。</p>
<p>hash结构如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190952.png" alt="1653992339937"></p>
<p>zset集合如下：</p>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190954.png" alt="1653992360355"></p>
<p>因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可：</p>
<p>Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value</p>
<p>当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：</p>
<ul>
<li>ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）</li>
<li>ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）</li>
</ul>
<p><img src="https://yichen-blog.oss-cn-beijing.aliyuncs.com//note-image/2023/07/16/20230716-190958.png" alt="1653992413406"></p>

      
    </div>
    <div class="article-footer">
      <blockquote class="mt-2x">
  <ul class="post-copyright list-unstyled">
    
    <li class="post-copyright-link hidden-xs">
      <strong>本文链接：</strong>
      <a href="https://yichenfirst.github.io/2023/03/20/redis/redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" title="redis底层数据结构" target="_blank" rel="external">https://yichenfirst.github.io/2023/03/20/redis/redis底层数据结构/</a>
    </li>
    
    <li class="post-copyright-license">
      <strong>版权声明： </strong> 本博客所有文章除特别声明外，均采用 <a href="http://creativecommons.org/licenses/by/4.0/deed.zh" target="_blank" rel="external">CC BY 4.0 CN协议</a> 许可协议。转载请注明出处！
    </li>
  </ul>
</blockquote>


<div class="panel panel-default panel-badger">
  <div class="panel-body">
    <figure class="media">
      <div class="media-left">
        <a href="" target="_blank" class="img-burn thumb-sm visible-lg">
          <img src="/images/avatar.jpg" class="img-rounded w-full" alt="">
        </a>
      </div>
      <div class="media-body">
        <h3 class="media-heading"><a href="" target="_blank"><span class="text-dark">逸辰</span><small class="ml-1x">后端开发</small></a></h3>
        <div>个人简介。</div>
      </div>
    </figure>
  </div>
</div>


    </div>
  </article>
  
    
  <section id="comments">
  	
      <div id="vcomments"></div>
    
  </section>


  
</div>

  <nav class="bar bar-footer clearfix" data-stick-bottom>
  <div class="bar-inner">
  
  <ul class="pager pull-left">
    
    <li class="prev">
      <a href="/2023/03/25/redis/redis%E5%86%85%E5%AD%98%E5%9B%9E%E6%94%B6/" title="redis内存回收"><i class="icon icon-angle-left" aria-hidden="true"></i><span>&nbsp;&nbsp;上一篇</span></a>
    </li>
    
    
    <li class="next">
      <a href="/2023/03/18/redis/redis%E9%AB%98%E5%8F%AF%E7%94%A8%E6%9C%BA%E5%88%B6/" title="redis高可用机制"><span>下一篇&nbsp;&nbsp;</span><i class="icon icon-angle-right" aria-hidden="true"></i></a>
    </li>
    
    
  </ul>
  
  
  <!-- Button trigger modal -->
  <button type="button" class="btn btn-fancy btn-donate pop-onhover bg-gradient-warning" data-toggle="modal" data-target="#donateModal"><span>赏</span></button>
  <!-- <div class="wave-icon wave-icon-danger btn-donate" data-toggle="modal" data-target="#donateModal">
    <div class="wave-circle"><span class="icon"><i class="icon icon-bill"></i></span></div>
  </div> -->
  
  
  <div class="bar-right">
    
  </div>
  </div>
</nav>
  
<!-- Modal -->
<div class="modal modal-center modal-small modal-xs-full fade" id="donateModal" tabindex="-1" role="dialog">
  <div class="modal-dialog" role="document">
    <div class="modal-content donate">
      <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
      <div class="modal-body">
        <div class="donate-box">
          <div class="donate-head">
            <p>感谢您的支持，我会继续努力的!</p>
          </div>
          <div class="tab-content">
            <div role="tabpanel" class="tab-pane fade active in" id="alipay">
              <div class="donate-payimg">
                <img src="/images/donate/alipayimg.png" alt="扫码支持" title="扫一扫" />
              </div>
              <p class="text-muted mv">扫码打赏，你说多少就多少</p>
              <p class="text-grey">打开支付宝扫一扫，即可进行扫码打赏哦</p>
            </div>
            <div role="tabpanel" class="tab-pane fade" id="wechatpay">
              <div class="donate-payimg">
                <img src="/images/donate/wechatpayimg.png" alt="扫码支持" title="扫一扫" />
              </div>
              <p class="text-muted mv">扫码打赏，你说多少就多少</p>
              <p class="text-grey">打开微信扫一扫，即可进行扫码打赏哦</p>
            </div>
          </div>
          <div class="donate-footer">
            <ul class="nav nav-tabs nav-justified" role="tablist">
              <li role="presentation" class="active">
                <a href="#alipay" id="alipay-tab" role="tab" data-toggle="tab" aria-controls="alipay" aria-expanded="true"><i class="icon icon-alipay"></i> 支付宝</a>
              </li>
              <li role="presentation" class="">
                <a href="#wechatpay" role="tab" id="wechatpay-tab" data-toggle="tab" aria-controls="wechatpay" aria-expanded="false"><i class="icon icon-wepay"></i> 微信支付</a>
              </li>
            </ul>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>



</main>

  <footer class="footer" itemscope itemtype="http://schema.org/WPFooter">
	
    <div class="copyright">
    	
        &copy; 2023 逸辰
        
        <div class="publishby">
        	Theme by <a href="https://github.com/cofess" target="_blank"> cofess </a>base on <a href="https://github.com/cofess/hexo-theme-pure" target="_blank">pure</a>.
        </div>
    </div>
</footer>
  <script src="//cdn.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js"></script>
<script>
window.jQuery || document.write('<script src="js/jquery.min.js"><\/script>')
</script>

<script src="/js/plugin.min.js"></script>


<script src="/js/application.js"></script>


    <script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(未命名)',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>

<script src="/js/insight.js"></script>






   
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>





   
    
  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/valine"></script>
  <script type="text/javascript">
  var GUEST = ['nick', 'mail', 'link'];
  var meta = 'nick,mail,link';
  meta = meta.split(',').filter(function(item) {
    return GUEST.indexOf(item) > -1;
  });
  new Valine({
    el: '#vcomments',
    verify: false,
    notify: false,
    appId: '',
    appKey: '',
    placeholder: 'Just go go',
    avatar: 'mm',
    meta: meta,
    pageSize: '10' || 10,
    visitor: false
  });
  </script>

     







</body>
</html>